package com.zp.self.module.level_4_算法练习.算法.二分查找;

/**
 * @author By ZengPeng
 */
public class 力扣_441_排列硬币 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_441_排列硬币().arrangeCoins(1));
        System.out.println(new 力扣_441_排列硬币().arrangeCoins(2));
        System.out.println(new 力扣_441_排列硬币().arrangeCoins(5));
        System.out.println(new 力扣_441_排列硬币().arrangeCoins(8));
        System.out.println(new 力扣_441_排列硬币().arrangeCoins(10));
        System.out.println(new 力扣_441_排列硬币().arrangeCoins(15));
        System.out.println(new 力扣_441_排列硬币().arrangeCoins(20));
        System.out.println(new 力扣_441_排列硬币().arrangeCoins(22));
        System.out.println(new 力扣_441_排列硬币().arrangeCoins(Integer.MAX_VALUE));
        System.out.println(new 力扣_441_排列硬币().arrangeCoins(1804289383));
    }

    /**
     * 题目：你总共有n枚硬币，并计划将它们按阶梯状排列。
     * 对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
     * 给你一个数字n ，计算并返回可形成 完整阶梯行 的总行数。
     *
     *
     * 分析：【perfect】
     *      1.直接减去 i个   超时了
     *      2.二分法  (n+n*n )/2    fun(n)>n  f(n-1)<n
     *
     * 边界值 & 注意点：
     *      1.
     **/
    public int arrangeCoins(int n) {
        long left =1;
        long right =(long) Math.sqrt(2d*n);
        while (left<=right){
            long mid = left+((right-left)>>1);
            long funMid = ((mid*mid-mid)>>1) +mid;
            if(funMid>n){
                right =mid-1;
            }else if(funMid<n){
                left=mid+1;
            }else return (int) mid;
        }
        return (int)right;
    }
}
